package datastrucure.tree;

/**
 * @Author Fizz Pu
 * @Date 2021/4/22 下午4:18
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import jdk.nashorn.api.tree.Tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 *     百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
 *     最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 *     例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
 */

public class LeeOffer68II {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // 思路一
        // 转化成链表 -> 链表最后一个交点问题
        ArrayList<TreeNode> listP = new ArrayList<>();
        ArrayList<TreeNode> listQ = new ArrayList<>();
        // search(root, p, listP);
        // search(root, q, listQ);
        traceBack(root, p, listP);
        traceBack(root, q, listQ);

        TreeNode resultNode = null;
        if(!listP.isEmpty() && !listQ.isEmpty()){
            Set<TreeNode> set = new HashSet<>(listP);
            for(TreeNode node : listQ){
                if(set.contains(node)){
                    resultNode = node;
                }
            }
        }

        return resultNode;
    }

    public static boolean traceBack(TreeNode root, TreeNode target, ArrayList<TreeNode> res){
        // 叶子节点
        if(root == null){
            return false;
        }

        res.add(root);

        // 遇到结果, 向上层返回
        if(root == target){
            return true;
        }

        boolean found = false;
        // 左子树
        if(root.left != null){
            found = traceBack(root.left, target, res);
        }

        // 左边子树中未发现则到右子树中寻找
        if(!found && root.right != null){
            found = traceBack(root.right, target, res);
        }

        // 左子树, 左右子树都没有找到, 则回溯
        if(!found) {res.remove(res.size() - 1);}

        return found;

    }

    private boolean search(TreeNode root, TreeNode targetNode, ArrayList<TreeNode> res){
        if(root == null){
            return false;
        }

        res.add(root);
        if(root == targetNode){
            return true;
        }

        boolean inLeft = false;
        boolean inRight = false;
        if(root.left != null){
            inLeft = search(root.left, targetNode, res);
        }

        if(!inLeft && root.right != null){
            inRight = search(root.right, targetNode, res);
        }

        if(!inLeft && !inRight) {
            res.remove(res.size() - 1);
        }
        return inLeft || inRight;
    }

    public static void main(String[] args) {
        TreeNode root = BuildTree.buildTestBinaryTree();
        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        // node5
        traceBack(root, root.left.right, treeNodes);
        System.out.println(treeNodes);
    }
}
